class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<j;i++,j--)
            swap(s[i],s[j]);
    }
};
class Solution {
public:
    bool isPalindrome(string s) {
        string tmp;
        for(int i=0;i<s.size();i++){
            if(s[i]>='a'&&s[i]<='z'||s[i]>='0'&&s[i]<='9')
                tmp+=(s[i]);
            if(s[i]>='A'&&s[i]<='Z')
                tmp+=(s[i]+32);
        }
        for(int left=0,right=tmp.size()-1;left<right;left++,right--)
            if(tmp[left]!=tmp[right])
                return false;
        return true;
    }
};
class Solution {
public:
    int minimumLength(string s) {
        int left = 0, right = s.size() - 1;
        while (left <= right) {
            bool t = false;
            while (left < right && s[left] == s[right]) {
                right--;
                t = true;
            }
            while (t&&left + 1 < right && s[left] == s[left + 1]) {
                left++;
            }
            // cout << left << ' ' << right << endl;
            if (!t)
                return right - left + 1;
            left++;
        }
        return 0;
    }
};
class Solution {
public:
    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
        int left = 0, right = plants.size() - 1, ans = 0;
        int node1 = capacityA, node2 = capacityB;
        while (left < right) {
            node1 -= plants[left++];
            node2 -= plants[right--];
            if (node1 < 0) {
                ans++, node1 = capacityA - plants[left - 1];
            }
            if (node2 < 0) {
                ans++, node2 = capacityB - plants[right + 1];
            }
        }
        if(left == right && node1 < plants[left] && node2 < plants[right])
            ans++;
        return ans;
    }
};
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        vector<int> ans(right + 1);
        int pos = right;
        while (left <= right) {
            int a = nums[left] + nums[right];
            if (a <= 0) {
                ans[pos--] = nums[left] * nums[left++];
            } else {
                ans[pos--] = nums[right] * nums[right--];
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        auto left_pos = arr.begin();
        int left = 0, right = arr.size() - 1;
        while (right - left >= k) {
            if (arr[right] - x >= x - arr[left]) {
                right--;
            } else {
                left++;
                left_pos++;
            }
        }
        return {left_pos,left_pos + k};
        return vector(left_pos,left_pos + k);
    }
};
class Solution {
public:
    vector<int> getStrongest(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        int left = 0, right = arr.size() - 1;
        vector<int> ans(k);
        int m = arr[(right) / 2];
        int pos = 0;
        while (left <= right && pos < k) {
            if (arr[left] - m + arr[right] - m < 0) {
                ans[pos++] = arr[left++];
            } else {
                ans[pos++] = arr[right--];
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int left = 0, right = numbers.size() - 1;
        while (right > left) {
            if (numbers[right] + numbers[left] > target)
                right--;
            else if (numbers[right] + numbers[left] < target)
                left++;
            else
                return {left + 1, right + 1};
        }
        return {0, 0};
    }
};
class Solution {
public:
    bool judgeSquareSum(int c) {
        vector<long long> vv;
        long long pos = 0;
        while (pos * pos <= c) {
            vv.emplace_back(pos * pos);
            pos++;
            // cout << pos << ' ';
        }
        int left = 0, right = pos - 1;
        while (left <= right) {
            if (vv[left] + vv[right] < c)
                left++;
            else if (vv[left] + vv[right] > c)
                right--;
            else
                return true;
        }
        return false;
    }
};
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int left = 0, right = nums.size() - 1, ans = 0;
        while (left < right) {
            while (left < right && nums[left] + nums[right] >= target)
                right--;
            if (left < right)
                ans += right - left;
            // cout << left << ' '<< right <<endl;
            left++;
        }
        return ans;
    }
};
class Solution {
public:
    int purchasePlans(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = 1e9 + 7;
        int left = 0, right = nums.size() - 1;
        int ans = 0;
        while (left < right) {
            while (left < right && nums[left] + nums[right] > target)
                right--;
            if (left < right)
                ans =(ans + right - left) % n;
            left++;
        }
        return ans;
    }
};
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i && x == nums[i - 1])
                continue;
            if (x + nums[i + 1] + nums[i + 2] > 0)
                break;
            if (x + nums[n - 2] + nums[n - 1] < 0)
                continue;
            int j = i + 1, k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s < 0)
                    j++;
                else if (s > 0)
                    k--;
                else {
                    ans.push_back({x, nums[j], nums[k]});
                    for (j++; j < k && nums[j] == nums[j - 1]; j++)
                        ; // 跳过重复数字
                    for (k--; k > j && nums[k] == nums[k + 1]; k--)
                        ; // 跳过重复数字
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ret = 1000000;
        for (int l = 0; l < n; l++) {
            int left = l + 1, right = n - 1;
            while (left < right) {
                int tmp = nums[l] + nums[left] + nums[right];
                if (abs(ret - target) > abs(tmp - target))
                    ret = tmp;
                if (tmp < target) {
                    left++;
                } else if (tmp > target) {
                    right--;
                } else {
                    return target;
                }
            }
        }
        return ret;
    }
};
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        ranges::sort(nums);
        vector<vector<int>> ans;
        int n = nums.size();
        for (int a = 0; a < n - 3; a++) { // 枚举第一个数
            long long x = nums[a]; // 使用 long long 避免溢出
            if (a > 0 && x == nums[a - 1]) continue; // 跳过重复数字
            if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break; // 优化一
            if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; // 优化二
            for (int b = a + 1; b < n - 2; b++) { // 枚举第二个数
                long long y = nums[b];
                if (b > a + 1 && y == nums[b - 1]) continue; // 跳过重复数字
                if (x + y + nums[b + 1] + nums[b + 2] > target) break; // 优化一
                if (x + y + nums[n - 2] + nums[n - 1] < target) continue; // 优化二
                int c = b + 1, d = n - 1;
                while (c < d) { // 双指针枚举第三个数和第四个数
                    long long s = x + y + nums[c] + nums[d]; // 四数之和
                    if (s > target) d--;
                    else if (s < target) c++;
                    else { // s == target
                        ans.push_back({(int) x, (int) y, nums[c], nums[d]});
                        for (c++; c < d && nums[c] == nums[c - 1]; c++); // 跳过重复数字
                        for (d--; d > c && nums[d] == nums[d + 1]; d--); // 跳过重复数字
                    }
                }
            }
        }
        return ans;
    }
};
    class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int l = 0, n = nums.size(), ret = 0;
        for (; l < n; l++) {
            if(nums[l] == 0) continue;
            int left = l + 1, right = l + 2;
            for (; left < n; left++) {
                while (right < n && nums[right] < nums[l] + nums[left]) {
                    right++;
                }
                ret += (right - left - 1);
            }
        }
        return ret;
    }
};


long long ans = 0;
using ll = long long;
class Solution {
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        ans = 0;
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        fun(nums1, nums2);
        fun(nums2, nums1);
        return ans;
    }
    void fun(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        for (int i = 0; i < n1; i++) {
            ll tmp = (ll)nums1[i] * nums1[i];
            int left = 0, right = n2 - 1;
            while (left < right) {
                if ((ll)nums2[left] * nums2[right] > tmp) {
                    right--;
                } else if ((ll)nums2[left] * nums2[right] < tmp)
                    left++;
                else {
                    if (nums2[left] == nums2[right]) {
                        ans += (ll)(right - left + 1) * (right - left) / 2;
                        break;
                    } else {
                        int cntleft = 1, cntright = 1;
                        cout << nums1[i] <<' ' << nums2[left] <<' '<< nums2[right]<<endl;
                        while (nums2[left] == nums2[left + 1])
                            left++, cntleft++;
                        while (nums2[right] == nums2[right - 1])
                            right--, cntright++;
                        left++,right--;
                        ans += cntleft * cntright;
                    }
                }
            }
        }
    }
};
int N = 1e9 + 7;
class Solution {
public:
    int threeSumMulti(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int ll = 0, n = arr.size(), ans = 0;
        for (; ll < n; ll++) {
            int left = ll + 1, right = n - 1;
            while (left < right) {
                int tmp = arr[ll] + arr[left] + arr[right];
                if (tmp > target) {
                    right--;
                } else if (tmp < target) {
                    left++;
                } else {
                    // 相等
                    if (arr[left] == arr[right]) {
                        ans = ans + (right - left + 1) * (right - left) / 2;
                        ans %= N;
                        break;
                    } else {
                        int cntleft = 1, cntright = 1;
                        while (arr[left] == arr[left + 1])
                            cntleft++, left++;
                        while (arr[right] == arr[right - 1])
                            cntright++, right--;
                        left++, right--;
                        ans = ans + cntleft * cntright;
                        ans %= N;
                    }
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        int n = tokens.size(), ans = 0, left = 0, right = n - 1, tmp = 0;
        sort(tokens.begin(), tokens.end());
        while (left <= right) {
            while (left <= right && power >= tokens[left]) {
                tmp++; // 能量
                power -= tokens[left++];
            }
            if (tmp == 0) {
                break;
            }
            ans = max(ans, tmp);
            tmp--;
            power += tokens[right--];
            // cout << left <<' ' << right <<endl;
        }
        return ans;
    }
};
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size(), ans = 0, left = 0, right = n - 1, tmp = 0;
        while (left < right) {
            ans =
                max(ans, min(height[left], height[right]) * (right - left));
            // cout << left << ' ' << right << endl;
            height[left] <height[right] ? left++:right--;
        }
        return ans;
    }
};
class Solution {
public:
    int trap(vector<int>& height) {
        int max_left = 0, max_right = 0, n = height.size(), left = 0, right = n - 1,
            ans = 0;
        while (left < right) {
            max_left = max(max_left, height[left]);
            max_right = max(max_right, height[right]);
            ans += (max_left > max_right ? max_right - height[right--]
                                         : max_left - height[left++]);
            //cout << ans << endl;
        }
        return ans;
    }
};
bool fun2(string& s, int left, int right) {
    while (left < right) {
        if (s[left++] != s[right--])
            return false;
    }
    return true;
}
bool fun(string& a, string& b) {
    int n = a.size(), left = 0, right = n - 1;
    while(left < right && a[left] == b[right])
        left++,right--;
    return fun2(a, left, right) || fun2(b, left, right);
}
class Solution {
public:
    bool checkPalindromeFormation(string a, string b) {
        return (fun(a, b) || fun(b, a));
    }
};
int N = 1e9 + 7;
vector<int> ff(1e6 + 6);
class Solution {
public:
    void fun(){
        ff[0] = 1;
        for(int i = 1;i < 100000;i++)
            ff[i] = (ff[i - 1] << 1) % N;
    }
    int numSubseq(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        if(ff[0] == 0)
            fun();
        int n = nums.size(),left = 0,right = n - 1,ans = 0;
        while(right >= left){
            if(nums[right] + nums[left] > target)
                right--;
            else{
                ans = (ans + ff[right - left])%N;
                left++;
            }
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> vv(n + 1);
        for(auto& e : edges){
            vv[e[0]]++;
            vv[e[1]]++;
        }
        sort(vv.begin().vv.end());
        vector<int> ret(queries.size());
        for(int i = 0;i < queries.size();i++)
        {
            int j = 1;
            for(;j <= n;j++){
                if(vv[j] <= queries[i])
                    j++;
            }
            ret[j] = n - j + 1;
        }
        return ret;
    }
};